﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics.Contracts;

namespace ConsoleApplication1
{
    class Move
    {
        public int X { get; set; }
        public int Y { get; set; }
    }

    class Program
    {

        static char[] charArray = new char[3] { 'a', 'b', 'c' };

        static void MyFun(object obj) { Console.WriteLine(obj); }
        static void MyFun(string obj) { Console.WriteLine(obj + "s"); }

        static void Main(string[] args)
        {
            BinaryRepresentation(10);
            Sum(3, 5);
            SumBinaryStrings("1100011", "0000010");
            FindTwoNonRepeatingIntegers(new int[] { 2, 4, 7, 9, 2, 4 });
            ReverseBits(8);
            PositionOfFirstSetBitFromRight(18);
            //CountSetBits(13);
            CountSpaces("This is a word");
            //GetTopK(new int[] { 3, 3, 2, 1, 45, 32, 1, 23, 4 }, 3);
            //Console.WriteLine("GetTopK");
            //LongestPalindrome("racecars");
            //PrintPermutationWithRepetition("ABCD");
            //Console.WriteLine(ReverseStringRecursrion("abcd"));
            //RemoveDuplicates(new int?[] { 1, 1, 1, 2, 2, 2, 3, 3, 3 });

            //Console.WriteLine("RemoveDuplicates");
            //bool canFormWord = WordBreak("ilikesamsung", new string[]{"mobile","samsung","sam","sung","man","mango",
            //               "icecream","and","go","i","like","ice","cream"});
            //Console.WriteLine(canFormWord);
            var start = new int[] { 1, 3, 0, 5, 8, 5 };
            var finish = new int[] { 2, 4, 6, 7, 9, 9 };
            ActivitySelection(start, finish);
            //var s = "geeks";
            //var minimumInsertions = MinimumInsertionstoFormPalindrome(s, 0, s.Length - 1);
            //Console.WriteLine(minimumInsertions);
            //var matrix = new int[,]  {{0, 1, 1, 0, 1},
            //       {1, 1, 0, 1, 0},
            //       {0, 1, 1, 1, 0},
            //       {1, 1, 1, 1, 0},
            //       {1, 1, 1, 1, 1},
            //       {0, 0, 0, 0, 0}};

            //GetMaxSubSquare(matrix);
            //var values = new int[] { 8, 15, 3, 7 };
            //int optimumValue = OptimalGameStrategy(values, 0, values.Length - 1);
            //Console.WriteLine(optimumValue);
            // var matrix = new int[,] 
            //{{1, 2, -1, -4, -20},
            //            {-8, -3, 4, 2, 1},
            //            {3, 8, 10, 1, 3},
            //            {-4, -1, 1, 7, -6}
            //           };

            // FindMaxSuminMatrix(matrix);
            //int k = 3;
            //FindKLargestElements(new int[] { 1, 23, 12, 9, 30, 2, 50 }, k);
            //int liss = LargestIndependentSetinTree(new Tree().root);
            //bool isSubsetSum = CheckIsSubSetSum(new int[] { 3, 34, 4, 12, 5, 2 }, 9);
            //Console.WriteLine(isSubsetSum);
            int editDistance = LevenshteinDistance("Cat", "Cars");
            Console.WriteLine(editDistance);
            int lcs = LongestCommonSubstring("OldSite:GeeksforGeeks.org", "NewSite:GeeksQuiz.com");
            Console.WriteLine(lcs);
            //int minCost = OptimalBinarySearchTree(new int[] { 34, 8, 50 }, 1);
            //Console.WriteLine(minCost);
            Action<string> action = MyFun;
            action("hello");
            //Console.WriteLine(PartitionProblem(new int[] { 1, 5, 11, 5 }));
            var pairs = new Move[]
            {
              new Move  {X=5,Y= 24},
              new Move   {X=39,Y=60},
                new Move {X=15,Y=28}, 
                new Move {X=27,Y=40},
new Move                 {X=50,Y=90}
            };
            //Console.WriteLine((MaximumLengthChainofPairs(pairs)));
            //string lcs = LongestCommonSubsequence("thisisatest", "testing123testing");
            //Console.WriteLine(LongestCommonSubsequence("BBABCBCAB", new string("BBABCBCAB".Reverse().ToArray())));
            //Console.WriteLine(LongestIncreasingSubsequence(new int[] { 3, 2, 6, 4, 5, 1 }));
            //Console.WriteLine("LongestIncreasingSubsequence");
            Console.WriteLine("Mine");
            //var perms = StringPermutation("abcd");
            //foreach (var item in perms)
            //{
            //    Console.WriteLine(item);
            //}
            //Console.WriteLine("Other");
            //perms = FindPermutations("abc");
            //foreach (var item in perms)
            //{
            //    Console.WriteLine(item);
            //}
            //int longestSubstring = LongestSubstringWithoutRepeatingCharacters("GEEKSFORGEEKS");
            //Console.WriteLine(longestSubstring);

            //int[,] path = new int[3, 3]
            //{
            //{ 1, 2, 3 }, 
            //{ 4, 8, 2 }, 
            //{ 1, 5, 3 } 
            //};

            //int initialCost = path[0, 0];
            //int cost = MinCostPath(path, 0, 0, 2, 2, initialCost);
            //Console.WriteLine("MinCostPath " + cost);
            //KnightsTour();
            //RatMaze();
            //NQueens();

            //var perms = FindPermutations("abc");
            //foreach (var token in perms)
            //{
            //    Console.WriteLine(token);
            //}


            Tree root = new Tree { root = new Node { item = 20 } };
            root.Insert(8);
            root.Insert(22);
            root.Insert(4);
            root.Insert(12);
            root.Insert(10);
            root.Insert(14);

            //GetKthSmallestNode(root.root, 3);

            //InsertionSort(new int[] { 1, 2, 4, 5, 3 });
            var sorted = MergeSort(new int[] { 1, 2, 4, 5, 3 });

            foreach (var item in sorted)
            {
                Console.WriteLine(item);
            }
            //Console.WriteLine(MinimumInRotatedSortedArray(new int[6] { 5, 6, 1, 2, 3, 4 }, 0, 5));
            //Console.WriteLine(MinimumInRotatedSortedArray(new int[4] { 1, 2, 3, 4 }, 0, 3));
            //Console.WriteLine(MinimumInRotatedSortedArray(new int[2] { 2, 1 }, 0, 1));
            RearrangeNegativeAndPositive(new int[] { -1, 2, -3, 4, 5, 6, -7, 8, 9 });
            //SortedSequenceOfSize3(new int[] { 12, 11, 10, 5, 6, 2, 30 });
            //CountSmaller(new int[] { 12, 1, 2, 3, 0, 11, 4 });
            //MaxDifference(new int[] { 2, 3, 10, 6, 4, 8, 1 });
            //ArraysUnion(new int[] { 1, 3, 4, 5, 7 }, new int[] { 2, 3, 5, 6 });
            //ArraysIntersection(new int[] { 1, 3, 4, 5, 7 }, new int[] { 2, 3, 5, 6 });
            //Leaders(new int[] { 16, 17, 4, 3, 5, 2 });
            //RotateArray(Enumerable.Range(1, 7).ToArray(), 2);
            //MedianTwoSortedArrays(new int[] { 1, 12, 15, 26, 38 },
            //        new int[] { 2, 13, 17, 30, 45 });
            //Node root = BuildTree(array: arr, start: 0, end: arr.Length);
            //BreadthTraversal(root);
            //QueueUsingStacks<int> qu = new QueueUsingStacks<int>();
            //qu.EnQueue(1);
            //qu.EnQueue(2);
            //qu.EnQueue(3);

            //for (int i = 0; i < qu.Count; i++)
            //{
            //    Console.WriteLine(qu.DeQueue());
            //}
            //PrintCount(new BitArray(5));
            //PrintCount(new HashSet<int> { 1, 2 });
            //PrintCount("ABC");
            //PrintCount("ABCDEF".Where(c => c > 'B'));
            //int? x = 3;
            //var z = x + null;
            //Console.WriteLine(z.HasValue);


            LLNode head = new LLNode();
            head.value = 1;

            head.next = new LLNode { value = 2 };
            head.next.next = new LLNode { value = 3 };
            head.next.next.next = new LLNode { value = 4 };
            var node5 = new LLNode { value = 5 };
            head.next.next.next.next = node5;
            head.next.next.next.next.next = new LLNode { value = 6 };
            //head.next.next.next.next.next = new LLNode { value = 5 };

            head.next.next.next.next.next.next = new LLNode { value = 7 };
            head.next.next.next.next.next.next.next = new LLNode { value = 8 };

            //InsertIntoSortedLL(head, 6);
            int x = 5;
            //GetNth(head, 7);
            //GetNth(head, 70);
            //DeleteNode(node5);
            //GetNthFromEnd(head, 3);
            //GetNthFromEnd(head, 30);
            //DeleteLinkedList(ref head);

            //var n = ReverseLinkedList(head);

            //MoveLastElement(head);

            LLNode palin = new LLNode { value = 10 };
            LLNode node2 = new LLNode { value = 20 };
            LLNode node3 = new LLNode { value = 30 };
            LLNode node4 = new LLNode { value = 30 };
            LLNode nodeFive = new LLNode { value = 20 };
            LLNode node6 = new LLNode { value = 10 };

            palin.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = nodeFive;
            nodeFive.next = node6;
            //MergeTwoLLAlternatively(head, palin);
            Console.WriteLine(CheckPalindrome(head));
            //Console.WriteLine(CheckPalindrome(palin));


            //LLNode head = new LLNode { value = 1 };
            //LLNode node2 = new LLNode { value = 2 };
            //LLNode node3 = new LLNode { value = 3 };
            //LLNode node4 = new LLNode { value = 4 };
            //LLNode node5 = new LLNode { value = 5 };
            //LLNode node6 = new LLNode { value = 6 };
            //LLNode node7 = new LLNode { value = 7 };
            //LLNode node8 = new LLNode { value = 8 };
            //LLNode node9 = new LLNode { value = 9 };

            /*
            LLNode head = new LLNode { value = 1 };
            LLNode node2 = new LLNode { value = 2 };
            LLNode node3 = new LLNode { value = 3 };
            LLNode node4 = new LLNode { value = 3 };
            LLNode node5 = new LLNode { value = 4 };
             * */
            //LLNode node5 = new LLNode { value = 5 };
            //LLNode node6 = new LLNode { value = 7 };
            //LLNode node7 = new LLNode { value = 8 };
            //LLNode node8 = new LLNode { value = 9 };
            //LLNode node9 = new LLNode { value = 10 };

            /*
            head.next = node2;
            head.next.next = node3;
            head.next.next.next = node4;
            head.next.next.next.next = node5;
             * */

            //head.next = node2;
            //node2.previous = head;

            //head.next.next = node3;
            //node3.previous = node2;

            //head.next.next.next = node4;
            //node4.previous = node3;
            //head.next.next.next.next = node5;
            //head.next.next.next.next.next = node6;
            //head.next.next.next.next.next.next = node7;
            //head.next.next.next.next.next.next.next = node8;
            //head.next.next.next.next.next.next.next.next = node9;

            LLNode a = null, b = null;
            //AlternatingSplit(ref a, ref b, head);
            //a = DeleteAlternate(head);
            //a = PairwiseSwap(head);
            //SplitCircularLinkedList(head, ref a, ref b);
            //ReverseDoublyLinkedList(ref head);
            //LLNode distinct = RemoveDuplicates(head);

            //var randomHead = new LLNodeRandom { Value = 1 };
            //var node2 = new LLNodeRandom { Value = 2 };
            //var node3 = new LLNodeRandom { Value = 3 };
            //var node4 = new LLNodeRandom { Value = 4 };
            //var node5 = new LLNodeRandom { Value = 5 };

            //randomHead.Next = node2;
            //randomHead.Next.Next = node3;
            //randomHead.Next.Next.Next = node4;
            //randomHead.Next.Next.Next.Next = node5;

            //LLNodeRandom copy = CopyRandomLinkedList(randomHead);

            //var one = InsertInCircularLinkedList(head, -1);
            //var two = InsertInCircularLinkedList(head, 6);
            //var three = InsertInCircularLinkedList(head, 20);

            //DeleteNodesWithGreaterValueOnrightSide(ref head);
            //LLNode f = ReverseAlternateNodesLinkedList(head, 3);

            //DeleteFirstNode(ref head);
            //int n = 1;

            //Node tree = MakeTreeFromLinkedList(head);

            //LLNode rotated = RotateLinkedListAtK(head, 4);
            ////rotated = RotateLinkedListByK(head, 4);

            //MergeSortLinkedList(ref rotated);
            //int n = 1;
            //LLNode list1 = new LLNode { value = 7 };
            //LLNode list1_2 = new LLNode { value = 8 };
            //LLNode list1_3 = new LLNode { value = 30 };
            //list1.random = list1_2;
            //list1.random.random = list1_3;


            //LLNode list2 = new LLNode { value = 20 };

            //LLNode list3 = new LLNode { value = 22 };
            //LLNode list3_2 = new LLNode { value = 50 };

            //list3.random = list3_2;

            //LLNode list4 = new LLNode { value = 35 };
            //LLNode list4_2 = new LLNode { value = 40 };
            //LLNode list4_3 = new LLNode { value = 45 };
            //list4.random = list4_2;
            //list4.random.random = list4_3;

            //head.random = list1;
            //node2.random = list2;
            //node3.random = list3;
            //node4.random = list4;

            //LLNode flattedned = FlatteningLinkedList(head);

            //var first = new LLNode { value = 5 };
            //var first_1 = new LLNode { value = 6 };
            //var first_2 = new LLNode { value = 3 };

            //first.next = first_1;
            //first.next.next = first_2;

            //var second = new LLNode { value = 8 };
            //var second_1 = new LLNode { value = 4 };
            //var second_2 = new LLNode { value = 2 };

            //second.next = second_1;
            //second.next.next = second_2;

            //int carry = 0;
            //LLNode sum = SumLinkedListLeastSignificant(first, second, ref carry);

            //carry = 0;
            //LLNode sum2 = SumLinkedListMostSignificant(first, second, ref carry);
            //if (carry == 1)
            //{
            //    sum2 = new LLNode { value = 1, next = sum2 };
            //}
            //head.next = node2;
            //head.next.next = node3;
            //head.next.next.next = node4;
            //head.next.next.next.next = node5;



            //LLNode loop = FindLoopInLinkedList(first);

            //DeleteNode(node3);
            //DeleteLinkedList(ref head);


            //head.random = node3;
            //node2.random = head;
            //node3.random = node5;
            //node4.random = node3;
            //node5.random = node2;

            //LLNode c = CopyLinkedList(head);

            //PrintLL(head);
            //var res = ReverseLL(n, 5);
            //PrintLL(res);
            var arr = new int[] { 16, 17, 4, 3, 5, 2 };
            nextGreatest(arr);

            //foreach (var item in arr)
            //{
            //Console.WriteLine(obj);
            //}

            //Tree theTree = new Tree();
            //theTree.Insert(1);

            //theTree.root.leftChild = new Node { item = 2 };

            //theTree.root.rightChild = new Node { item = 3 };

            //theTree.root.leftChild.leftChild = new Node { item = 4 };
            //theTree.root.leftChild.rightChild = new Node { item = 5 };

            //theTree.root.rightChild.leftChild = new Node { item = 6 };
            //theTree.root.rightChild.rightChild = new Node { item = 7 };


            //Tree theTree = new Tree();
            //theTree.Insert(20);

            //theTree.root.leftChild = new Node { item = 8 };

            //theTree.root.rightChild = new Node { item = 22 };

            //theTree.root.leftChild.leftChild = new Node { item = 4 };
            //theTree.root.leftChild.rightChild = new Node { item = 12 };

            //theTree.root.leftChild.rightChild.leftChild = new Node { item = 10 };
            //theTree.root.leftChild.rightChild.rightChild = new Node { item = 14 };

            Tree bigTree = new Tree();
            bigTree.Insert(26);

            bigTree.root.leftChild = new Node { item = 10 };

            bigTree.root.rightChild = new Node { item = 3 };

            bigTree.root.leftChild.leftChild = new Node { item = 4 };
            bigTree.root.leftChild.rightChild = new Node { item = 6 };

            bigTree.root.rightChild.leftChild = new Node { item = 3 };

            //Console.WriteLine(CheckSumPath(bigTree.root, 40));
            //Console.WriteLine(GetNodeLevel(bigTree.root, 4, 1));

            Tree smallTree = new Tree();
            smallTree.Insert(10);
            smallTree.root.leftChild = new Node { item = 4 };
            smallTree.root.rightChild = new Node { item = 6 };

            //InOrderTraversalWithoutRecursion(bigTree.root);
            //DeleteTree(ref smallTree.root);

            Tree treeWithBSTSubset = new Tree();
            treeWithBSTSubset.root = new Node { item = 50 };
            treeWithBSTSubset.root.leftChild = new Node { item = 30 };
            treeWithBSTSubset.root.rightChild = new Node { item = 60 };

            treeWithBSTSubset.root.leftChild.leftChild = new Node { item = 5 };
            treeWithBSTSubset.root.leftChild.rightChild = new Node { item = 20 };

            treeWithBSTSubset.root.rightChild.leftChild = new Node { item = 45 };
            treeWithBSTSubset.root.rightChild.rightChild = new Node { item = 70 };

            treeWithBSTSubset.root.rightChild.rightChild.leftChild = new Node { item = 65 };
            treeWithBSTSubset.root.rightChild.rightChild.rightChild = new Node { item = 80 };

            //bool isSumTree = CheckIsSumTree(bigTree.root);
            //bool isSubSet = CheckIsSubSet(bigTree.root, smallTree.root);
            //Console.WriteLine(isSubSet);

            Node next = null;
            //PopulateInorderSuccessor(bigTree.root,ref next);

            int totalSize = 0;
            int sizeSoFar = 0;
            SizeOfLargestBSTSubtree(treeWithBSTSubset.root, ref totalSize, ref sizeSoFar);
            //Console.WriteLine(totalSize);
            //ConnectNodesAtSameLevel(bigTree.root);

            //int s = FindKSmallestElement(theTree.root, 3);
            //int s = GetNodeLevel(theTree.root, 10);
            //Console.WriteLine(s);

            //PrintAncestorsOfNode(theTree.root, 10, new List<Node>());

            //BreadthTraversalUsingQueue(bigTree.root);

            //int count = CountLeafNodes(theTree.root);

            //ConvertTreeToChildrenSum(theTree.root);

            //InOrderTraversalWithoutRecursion(theTree.root);

            //PrintAllPathsFromRootToLeaf(theTree.root, new List<Node>());

            //bool hasPathSum = HasPathSum(theTree.root, 7);
            //Console.WriteLine(hasPathSum);

            //PrintNodesAtKDistanceFromRoot(theTree.root, 2);

            //Node lca = FindLowestCommonAncestor(theTree.root, 1, 4);

            //Tree anotherTree = new Tree();
            //anotherTree.Insert(2);
            //anotherTree.root.leftChild = new Node { item = 1 };
            //anotherTree.root.rightChild = new Node { item = 3 };

            //theTree.Insert(4);
            //theTree.Insert(5);
            //int size = GetTreeSize(theTree.root);
            //bool bb = TreesAreEqual(theTree.root, anotherTree.root);
            //int treeHeight = GetTreeHeight(theTree.root);
            //MirrorTree(ref theTree.root);
            //theTree.Inorder(theTree.root);
            //DeleteTree(ref theTree.root);
            //theTree.Inorder(theTree.root);

            //var tree = new Tree();
            //tree.Insert(20);
            //tree.root.leftChild = new Node() { item = 8 };
            //tree.root.rightChild = new Node() { item = 22 };

            //tree.root.leftChild.leftChild = new Node() { item = 4 };
            //tree.root.leftChild.rightChild = new Node() { item = 12 };

            //tree.root.leftChild.rightChild.leftChild = new Node() { item = 10 };
            //tree.root.leftChild.rightChild.rightChild = new Node() { item = 14 };

            //tree.root.rightChild.rightChild = new Node() { item = 25 };


            var tree = new Tree();
            tree.Insert(1);
            tree.root.leftChild = new Node() { item = 2 };
            tree.root.rightChild = new Node() { item = 3 };

            tree.root.leftChild.leftChild = new Node() { item = 4 };
            tree.root.leftChild.rightChild = new Node() { item = 5 };

            tree.root.leftChild.leftChild.leftChild = new Node() { item = 7 };
            tree.root.leftChild.leftChild.rightChild = new Node() { item = 8 };

            tree.root.rightChild.rightChild = new Node() { item = 6 };
            tree.root.rightChild.rightChild.leftChild = new Node() { item = 9 };
            tree.root.rightChild.rightChild.rightChild = new Node() { item = 10 };


            var llHead = new LLNode();

            //ConvertTreeToLinkedList(tree.root, ref llHead);
            //Console.WriteLine("ConvertTreeToDLL");
            //PrintLL(llHead);

            llHead = null;
            ExtractTreeLeavesToDLL(tree.root, ref llHead);
            var prev = llHead.previous;

            while (prev != null)
            {
                prev = prev.previous;
                llHead = llHead.previous;
            }
            PrintLL(llHead);
            //Console.WriteLine("height:" + GetHeight(tree.root).ToString());
            //Console.WriteLine("GetHeightUsingStack:" + GetHeightUsingStack(tree.root).ToString());
            //tree.Postorder(tree.root);


            //BreadthTraversal(tree.root);
            //Console.Read();


            //int x = 5;
            ////Console.WriteLine(Convert.ToString(-x, 2));

            //int[] a = new int[] { 1, 2, 3, 4, 5 };
            //int[] b = new int[] { 2, 5 };
            //int i = 0, j = 0;
            //List<int> final = new List<int>();

            ////while (b[j] > a[i])
            ////{
            ////    final.Add(a[i]);
            ////    j++;
            ////}

            //while (i < a.Length && j < b.Length)
            //{
            //    if (a[i] < b[j])
            //    {
            //        i++;
            //    }
            //    else
            //    {
            //        final.Add(a[i]);

            //        j++;
            //    }
            //    //dont do anything for the equality case. 
            //}
            //final.ForEach(e => Console.WriteLine(e));
            //t.Postorder(t.root);
            //BreadthTraversal(t.root);
            //int min = GetMin(t.root.leftChild);
            //Console.WriteLine(min);

            int max = GetMax(treeWithBSTSubset.root);
            Console.WriteLine(max);

            //bool isBST = CheckIsBST(t.root, min, max);
            //Console.WriteLine(isBST);

            //int[] ar = new int[] { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
            //arrange(ar, ar.Length);

            //foreach (var item in ar)
            //{
            //    Console.Write(item + " ");
            //}
            //Node parent = LCA(tree.root, tree.root.leftChild.leftChild, tree.root.leftChild.rightChild.rightChild);
            //Console.WriteLine(parent.item);
            //BoundaryTraversal(t.root);


            //int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
            //int first, second;
            //int[] arr = new int[] { };
            //for (first = 1; first <= 5; ++first)
            //    for (second = 1; second <= 5; ++second)
            //        arr[(first + second - 1) % 7]++;

            //for (first = 0; first < 7; ++first)
            //    Console.WriteLine("{0}:{1}", first + 1, arr[first]);
            //int[] a = new int[6] { 3, 2, 1, 5, 0, 2 };
            //CountSort(a, 5);

            //string str = "ABCD";
            //GetCombinations(str);
            //int x = 0;
            //for (int i = 0; i < 5; i++)
            //{
            //    for (int j = i; j < 5; j++)
            //    {
            //        //Console.WriteLine(i);

            //        Console.WriteLine(++x);
            //    }
            //}
            //var ff = GetCombinations(str, 0);
            //foreach (var item in ff)
            //{
            //    Console.WriteLine(item);
            //}

            //int[] sorted = InsertionSort(a);
            //int[] sorted = MergeSort(a);
            ////QuickSort(a, 0, a.Length - 1);
            ////int[] sorted = a;
            //List<int> arr = new List<int>();
            //QuickSelect(a, 0, a.Length - 1, 2, arr);

            //MinHeap<int> minHeap = new MinHeap<int>();
            //minHeap.Insert(14);
            //minHeap.Insert(10);
            //minHeap.Insert(16);

            //Console.WriteLine(arr[0]);
            //Console.WriteLine(arr[1]);

            //foreach (var item in sorted)
            //{
            //    Console.WriteLine(item);
            //}
        }

        private static void combinationUtil(int[] arr, int[] data, int start, int index, int k)
        {
            if (index == k)
            {
                foreach (var item in data)
                {
                    Console.Write(item);
                } Console.WriteLine();
            }

            for (int i = start; i < arr.Length && arr.Length - i + 1 >= k - index; i++)
            {
                data[index] = arr[i];
                combinationUtil(arr, data, i + 1, index + 1, k);
            }
        }

        private static void SumBinaryStrings(string a, string b)
        {
            var carry = 0;
            var sum = "";

            for (int i = a.Length - 1; i > -1; i--)
            {
                var first = a[i] == '0' ? 0 : 1;
                var second = b[i] == '0' ? 0 : 1;

                var tmpSum = first ^ second ^ carry;
                sum = tmpSum.ToString() + sum;

                carry = (first & second) | (second | carry) | (first & carry);
            }
            if (carry != 0)
            {
                sum = "1" + sum;
            }
            Console.WriteLine("Sum is: " + sum);
        }

        private static void BinaryRepresentation(int n)
        {
            var representation = "";

            while (n != 0)
            {
                representation += (n & 1);
                n >>= 1;
            }
            Console.WriteLine(new string(representation.Reverse().ToArray()));
        }

        private static void Sum(int a, int b)
        {
            while (b != 0)
            {
                var carry = a & b;
                a ^= b;
                b = carry << 1;
            }

            Console.WriteLine(a);
        }

        private static void FindTwoNonRepeatingIntegers(int[] arr)
        {
            var xorAll = 0;

            foreach (var item in arr)
            {
                xorAll ^= item;
            }

            var positionOfFirstSetBit = PositionOfFirstSetBitFromRight(xorAll);

            int x = 0, y = 0;
            foreach (var item in arr)
            {
                if ((item ^ positionOfFirstSetBit) != 0)
                {
                    x ^= item;
                }
                else
                {
                    y ^= item;
                }
            }
            int f = 0;

        }

        private static void ReverseBits(int num)
        {
            Console.WriteLine("ReverseBits");
            var reverseNum = 0;

            while (num != 0)
            {
                if ((num & 1) == 1)
                {
                    reverseNum++;
                }

                num = num >> 1;
                reverseNum = reverseNum << 1;
            }
            Console.WriteLine(reverseNum);
        }

        private static int PositionOfFirstSetBitFromRight(int n)
        {
            var pos = 1;

            while (n != 0)
            {
                if ((n & 1) == 1)
                {
                    break;
                }
                n = n >> 1;
                pos++;
            }
            Console.WriteLine("PositionOfFirstSetBitFromRight");
            Console.WriteLine(pos);

            return pos;
        }

        private static void CountSetBits(int n)
        {
            var count = 0;

            while (n != 0)
            {
                n = n & (n - 1);
                count++;
            }

            Console.WriteLine(count);


        }

        private static void CountSpaces(string token)
        {
            var insideWord = true;
            var count = 0;

            foreach (var c in token)
            {
                if (c == ' ')
                {
                    insideWord = false;
                }
                else
                {
                    if (!insideWord)
                    {
                        count++;
                    }
                    insideWord = true;
                }
            }

            Console.WriteLine(count);
        }

        private static void LongestPalindrome(string str)
        {
            var dictionary = new Dictionary<string, int>();
            var maxPalin = "";

            for (int i = 1; i < str.Length; i++)
            {
                string palin = str[i].ToString();

                for (int j = i - 1, k = i + 1; j > -1 && k < str.Length; j--, k++)
                {
                    if (str[j] == str[k])
                    {
                        palin = str[j].ToString() + palin + str[k].ToString();
                    }
                    if (palin.Length > maxPalin.Length)
                    {
                        maxPalin = palin;
                    }
                }
            }

            Console.WriteLine(maxPalin);
        }

        private static void PrintPermutationWithRepetition(string str)
        {
            var data = new char[str.Length];
            PrintPermutationWithRepetitionRecursive(str, data, str.Length - 1, 0);
        }

        private static void PrintPermutationWithRepetitionRecursive(string str, char[] data, int last, int index)
        {
            for (int i = 0; i < str.Length; i++)
            {
                data[index] = str[i];

                if (last == index)
                {
                    Console.WriteLine(data);
                }
                else
                {
                    PrintPermutationWithRepetitionRecursive(str, data, last, index + 1);
                }
            }
        }

        private static string ReverseStringRecursrion(string str)
        {
            if (str.Length == 0)
            {
                return string.Empty;
            }
            if (str.Length == 1)
            {
                return str;
            }

            return ReverseStringRecursrion(str.Substring(1)) + str[0];
        }

        private static void RemoveDuplicates(int?[] arr)
        {
            var first = 0;
            var second = 1;

            while (second < arr.Length)
            {
                while (arr[first] == arr[second])
                {
                    arr[second] = null;
                    second++;

                    if (second == arr.Length)
                    {
                        break;
                    }
                }

                first = second;
                second++;
            }

            for (first = 0; first < arr.Length - 1; first++)
            {
                if (arr[first] == null)
                {
                    break;
                }
            }

            second = first + 1;
            int count = 0;

            while (second != arr.Length - 1)
            {
                while (arr[second] == null)
                {
                    second++;
                    if (second >= arr.Length - 1)
                    {
                        break;
                    }
                }
                if (second >= arr.Length - 1)
                {
                    break;
                }
                arr[first] = arr[second];
                first++;
                second++;
                count++;
            }
            for (first = 0; first <= count; first++)
            {
                Console.WriteLine(arr[first]);
            }
        }

        private static IEnumerable<string> StringPermutation(string a)
        {
            if (a.Length < 2)
            {
                yield return a;
            }
            else if (a.Length == 2)
            {
                yield return a;
                yield return a[1].ToString() + a[0].ToString();
            }
            else
            {
                var firstCharacter = a[0];
                var permutations = StringPermutation(a.Substring(1));

                foreach (var item in permutations)
                {
                    var newString = firstCharacter + item;
                    yield return newString;
                    var arr = newString.ToArray();

                    for (int i = 0; i < arr.Length - 1; i++)
                    {
                        var tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        yield return new String(arr);
                    }
                }
            }
        }

        private static void ActivitySelection(int[] start, int[] finish)
        {
            List<Move> activites = new List<Move>();
            for (int i = 0; i < start.Length; i++)
            {
                activites.Add(new Move { X = start[i], Y = finish[i] });
            }
            activites = activites.OrderBy(a => a.Y).ToList();

            var currentActivity = activites[0];
            Console.WriteLine(currentActivity.X);

            for (int i = 1; i < activites.Count; i++)
            {
                if (activites[i].X >= currentActivity.Y)
                {

                    currentActivity = activites[i];
                    Console.WriteLine(currentActivity.X);
                }
            }
        }

        private static bool WordBreak(string token, string[] dictionary)
        {
            if (token.Length == 0)
            {
                return true;
            }

            for (int i = 0; i < token.Length; i++)
            {
                var substring = token.Substring(0, i + 1);
                if (dictionary.Contains(substring))
                {
                    token = token.Substring(i + 1, token.Length - 1 - i);
                    return WordBreak(token, dictionary);
                }
            }

            return false;
        }

        private static int MinimumInsertionstoFormPalindrome(string s, int start, int end)
        {
            if (start > end)
            {
                return int.MaxValue;
            }
            if (start == end)
            {
                return 0;
            }
            if (start + 1 == end)
            {
                if (s[start] == s[end])
                {
                    return 0;
                }

                return 1;
            }
            if (s[start] == s[end])
            {
                return MinimumInsertionstoFormPalindrome(s, start + 1, end - 1);
            }

            return 1 + Math.Min(MinimumInsertionstoFormPalindrome(s, start + 1, end), MinimumInsertionstoFormPalindrome(s, start, end - 1));
        }

        private static void GetMaxSubSquare(int[,] matrix)
        {
            var row = matrix.GetLength(0);
            var col = matrix.GetLength(1);
            var result = new int[row, col];

            for (int i = 0; i < row; i++)
            {
                result[i, 0] = matrix[i, 0];
            }
            for (int j = 0; j < col; j++)
            {
                result[0, j] = matrix[0, j];
            }

            var max = 0;

            for (int i = 1; i < row; i++)
            {
                for (int j = 1; j < col; j++)
                {
                    if (matrix[i - 1, j - 1] == 1)
                    {
                        result[i, j] = 1 + Math.Min(result[i - 1, j - 1], Math.Min(result[i - 1, j], result[i, j - 1]));
                        max = Math.Max(result[i, j], max);
                    }
                }
            }

            Console.WriteLine(max);
        }

        private static int OptimalGameStrategy(int[] arr, int start, int end)
        {
            if (start == end)
            {
                return arr[start];
            }
            if (start + 1 == end)
            {
                return Math.Max(arr[start], arr[end]);
            }

            int firstCoinSelected = arr[start] + Math.Min(OptimalGameStrategy(arr, start + 2, end), OptimalGameStrategy(arr, start + 1, end - 1));
            int lastCoinSelected = arr[end] + Math.Min(OptimalGameStrategy(arr, start + 1, end - 1), OptimalGameStrategy(arr, start, end - 2));

            return Math.Max(firstCoinSelected, lastCoinSelected);
        }

        static void FindMaxSuminMatrix(int[,] matrix)
        {
            var row = matrix.GetLength(0);
            var col = matrix.GetLength(1);
            var maxSum = 0;

            for (int i = 0; i < col; i++)
            {
                var tmp = new int[row];

                for (int j = i; j < col; j++)
                {
                    for (int k = 0; k < row; k++)
                    {
                        tmp[k] += matrix[k, j];
                    }

                    var kadane = MaxContigousSum(tmp);
                    maxSum = Math.Max(maxSum, kadane);
                }
            }

            Console.WriteLine(maxSum);
        }

        private static int MaxContigousSum(int[] tmp)
        {
            int maxTillNow = 0, maxOverAll = 0;

            foreach (var item in tmp)
            {
                maxTillNow += item;

                if (maxTillNow < 0)
                {
                    maxTillNow = 0;
                }
                else
                {
                    if (maxOverAll < maxTillNow)
                    {
                        maxOverAll = maxTillNow;
                    }
                }
            }

            return maxOverAll;
        }

        static int Kadane(int[] arr, ref int start, ref int finish, int n)
        {
            // initialize sum, maxSum and
            int sum = 0, maxSum = int.MinValue, i;

            // Just some initial value to check for all negative values case
            finish = -1;

            // local variable
            int local_start = 0;

            for (i = 0; i < n; ++i)
            {
                sum += arr[i];

                if (sum < 0)
                {
                    sum = 0;
                    local_start = i + 1;
                }
                else if (sum > maxSum)
                {
                    maxSum = sum;
                    start = local_start;
                    finish = i;
                }
            }

            // There is at-least one non-negative number
            if (finish != -1)
                return maxSum;

            // Special Case: When all numbers in arr[] are negative
            maxSum = arr[0];
            start = finish = 0;

            // Find the maximum element in array
            for (i = 1; i < n; i++)
            {
                if (arr[i] > maxSum)
                {
                    maxSum = arr[i];
                    start = finish = i;
                }
            }

            return maxSum;
        }

        private static int LevenshteinDistance(string a, string b)
        {
            var matrix = new int[a.Length + 1, b.Length + 1];

            for (int i = 0; i < a.Length + 1; i++)
            {
                matrix[i, 0] = i;
            }
            for (int j = 0; j < b.Length + 1; j++)
            {
                matrix[0, j] = j;
            }
            for (int i = 1; i < a.Length + 1; i++)
            {
                for (int j = 1; j < b.Length + 1; j++)
                {
                    if (a[i - 1] == b[j - 1])
                    {
                        matrix[i, j] = matrix[i - 1, j - 1];//no operation
                    }
                    else
                    {
                        matrix[i, j] = 1 + Math.Min(matrix[i - 1, j - 1], Math.Min(matrix[i - 1, j], matrix[i, j - 1]));
                    }
                }
            }

            return matrix[a.Length, b.Length];
        }

        private static int LongestCommonSubstring(string a, string b)
        {
            var matrix = new int[a.Length + 1, b.Length + 1];
            var result = 0;

            for (int i = 1; i < a.Length + 1; i++)
            {
                for (int j = 1; j < b.Length + 1; j++)
                {
                    if (a[i - 1] == b[j - 1])
                    {
                        matrix[i, j] = 1 + matrix[i - 1, j - 1];
                        result = Math.Max(result, matrix[i, j]);
                    }
                }
            }

            return result;
        }

        private static int LargestIndependentSetinTree(Node root)
        {
            if (root == null)
            {
                return 0;
            }

            var exclude = LargestIndependentSetinTree(root.leftChild) + LargestIndependentSetinTree(root.rightChild);
            var include = 1;

            if (root.leftChild != null)
            {
                include += LargestIndependentSetinTree(root.leftChild.leftChild)
                    + LargestIndependentSetinTree(root.leftChild.rightChild);
            }
            if (root.rightChild != null)
            {
                include += LargestIndependentSetinTree(root.rightChild.leftChild)
                    + LargestIndependentSetinTree(root.rightChild.rightChild);
            }

            return Math.Max(include, exclude);
        }

        private static bool CheckIsSubSetSum(int[] arr, int sum)
        {
            if (sum == 0)
            {
                return true;
            }
            if (arr.Length == 0)
            {
                return false;
            }

            var list = arr.ToList();
            var lastElement = list[list.Count - 1];
            list.RemoveAt(list.Count - 1);

            return CheckIsSubSetSum(list.ToArray(), sum) || CheckIsSubSetSum(list.ToArray(), sum - lastElement);
        }

        private static int OptimalBinarySearchTree(int[] freq, int level)
        {
            if (freq.Length == 0)
            {
                return 0;
            }
            if (freq.Length == 0)
            {
                return freq[0];
            }

            int min = int.MaxValue;
            var nextLevel = level + 1;

            for (int i = 0; i < freq.Length; i++)
            {
                var left = freq.Take(i);
                var right = freq.Skip(i + 1).Take(freq.Length - i - 1);
                var calc = freq[i] * level
                    + left.Sum() * (level + 1)
                    + right.Sum() * (level + 1);
                calc += OptimalBinarySearchTree(left.ToArray(), nextLevel)
                    + OptimalBinarySearchTree(right.ToArray(), nextLevel);

                if (min > calc)
                {
                    min = calc;
                }
            }

            return min;
        }

        private static void FindKLargestElements(int[] arr, int k)
        {

            var tmpArr = new int[k];
            int i = 0;

            for (; i < k; i++)
            {
                tmpArr[i] = arr[i];
            }

            for (; i < arr.Length; i++)
            {
                int minIdx = 0;
                int min = tmpArr[minIdx];
                GetMin(tmpArr, ref min, ref minIdx);

                if (min < arr[i])
                {
                    tmpArr[minIdx] = arr[i];
                }
            }

            for (int j = 0; j < tmpArr.Length; j++)
            {
                Console.WriteLine(tmpArr[j]);
            }
        }

        private static void GetMin(int[] tmpArr, ref int min, ref int minIdx)
        {
            for (int j = 1; j < tmpArr.Length; j++)
            {
                if (min > tmpArr[j])
                {
                    min = tmpArr[j];
                    minIdx = j;
                }
            }
        }

        private static int MaximumLengthChainofPairs(Move[] pairs)
        {
            var list = new List<List<Move>>();
            list.Add(new List<Move>() { pairs[0] });

            for (int current = 1; current < pairs.Length; current++)
            {
                list.Add(new List<Move>());

                for (int prev = 0; prev < current; prev++)
                {
                    var prevList = list[prev];
                    var lastElementinPrev = prevList[prevList.Count - 1].Y;

                    var currentList = list[current];
                    var firstElementinCurrent = pairs[current].X;

                    if (prevList.Count > currentList.Count && lastElementinPrev <= firstElementinCurrent)
                    {
                        list[current] = new List<Move>(prevList);
                    }
                }

                list[current].Add(pairs[current]);
            }

            return list.Max(s => s.Count);
        }

        private static bool PartitionProblem(int[] arr)
        {
            var sum = arr.Sum();

            if (sum % 2 != 0)
            {
                return false;
            }

            sum /= 2;

            return PartitionProblemUtil(arr, sum);
        }

        private static bool PartitionProblemUtil(int[] arr, int sum)
        {
            if (sum == 0)
            {
                return true;
            }

            if (arr.Length == 0)
            {
                return false;
            }

            var lst = new List<int>(arr);
            lst.RemoveAt(arr.Length - 1);

            var sumDecreased = PartitionProblemUtil(lst.ToArray(), sum - arr[arr.Length - 1]);
            var arrayDecreased = PartitionProblemUtil(lst.ToArray(), sum);

            return sumDecreased || arrayDecreased;
        }

        private static string LongestCommonSubsequence(string a, string b)
        {
            if (a.Length == 0 || b.Length == 0)
            {
                return string.Empty;
            }

            var aSub = a.Substring(0, a.Length - 1);
            var bSub = b.Substring(0, b.Length - 1);

            if (a[a.Length - 1] == b[b.Length - 1])
            {
                return LongestCommonSubsequence(aSub, bSub) + a[a.Length - 1];
            }

            var x = LongestCommonSubsequence(aSub, b);
            var y = LongestCommonSubsequence(a, bSub);

            if (x.Length > y.Length)
            {
                return x;
            }

            return y;
        }

        private static int MaxJumpstoReachEndofArray(int[] arr)
        {
            int maxJumps = 0;

            int start = 0;

            while (start < arr.Length - 1)
            {
                maxJumps++;
                int max = 0;
                var limit = Math.Min(arr[start], arr.Length);
                var idx = start;

                for (int i = 0; i < limit; i++)
                {
                    var pos = arr[i + start];

                    if (max < arr[pos])
                    {
                        max = arr[pos];
                        idx = pos;
                    }
                }

                start = idx;

            }

            return maxJumps;

        }

        private static int LongestSubstringWithoutRepeatingCharacters(string s)
        {
            var set = new HashSet<char>();
            int sum = 0;
            int sumOverAll = 0;

            foreach (char c in s)
            {
                if (set.Contains(c))
                {
                    set = new HashSet<char>();
                    sum = 0;
                }
                else
                {
                    sum++;
                    set.Add(c);
                }

                sumOverAll = Math.Max(sum, sumOverAll);
            }

            return sumOverAll;
        }

        private static int MinCostPath(int[,] arr, int startX, int startY, int endX, int endY, int initialCost)
        {
            if (startX == endX && startY == endY)
            {
                return initialCost;
            }

            int down = int.MaxValue;
            int right = int.MaxValue;
            int diagonal = int.MaxValue;

            if (startY + 1 < arr.GetLength(1))
            {
                down = MinCostPath(arr, startX, startY + 1, endX, endY, initialCost + arr[startX, startY + 1]);
            }
            if (startX + 1 < arr.GetLength(0))
            {
                right = MinCostPath(arr, startX + 1, startY, endX, endY, initialCost + arr[startX + 1, startY]);
            }
            if (startX + 1 < arr.GetLength(0) && startY + 1 < arr.GetLength(1))
            {
                diagonal = MinCostPath(arr, startX + 1, startY + 1, endX, endY, initialCost + arr[startX + 1, startY + 1]);
            }

            return Math.Min(down, Math.Min(right, diagonal));
        }

        private static int LongestIncreasingSubsequence(int[] arr)
        {
            var list = new List<List<int>>();
            list.Add(new List<int> { arr[0] });

            for (int i = 1; i < arr.Length; i++)
            {
                list.Add(new List<int>());

                for (int j = i - 1; j > -1; j--)
                {
                    var subList = list[j];
                    var lastElement = subList[subList.Count - 1];

                    if (lastElement < arr[i] && subList.Count > list[i].Count)
                    {
                        list[i] = new List<int>(subList);
                    }
                }

                list[i].Add(arr[i]);
            }

            return list.Max(l => l.Count);

        }

        private static void GetTopK(int[] arr, int k)
        {
            var heap = new PriorityQueue();
            int i = 0;

            for (int j = 0; j < k; i++, j++)
            {
                heap.Insert(arr[j]);
            }

            for (; i < arr.Length; i++)
            {
                if (arr[i] > heap.Min)
                {
                    heap.RemoveMin();
                    heap.Insert(arr[i]);
                }
            }

            foreach (var item in heap.Items)
            {
                Console.WriteLine(item);
            }
        }

        private static void NQueens()
        {
            var board = new int[4, 4];

            if (NQueensUtil(board, 0))
            {
                PrintNQueens(board);
            }
            else
            {
                Console.WriteLine("no solution");
            }
        }

        private static bool NQueensUtil(int[,] board, int n)
        {
            if (n == board.GetLength(0))
            {
                return true;
            }

            for (int i = 0; i < board.GetLength(0); i++)
            {
                if (CheckQueenPlacementIsSafe(board, n, i))
                {
                    board[n, i] = 1;
                    n++;

                    if (NQueensUtil(board, n))
                    {
                        return true;
                    }

                    n--;
                    board[n, i] = 0;
                }
            }

            return false;
        }

        private static bool CheckQueenPlacementIsSafe(int[,] board, int row, int col)
        {
            for (int i = 0; i < board.GetLength(0); i++)
            {
                if ((board[row, i] == 1 && i != col) || (board[i, col] == 1 && i != row))
                {
                    return false;
                }
            }

            for (int i = row + 1, j = col + 1; i < board.GetLength(0) && j < board.GetLength(1); i++, j++)
            {
                if (board[i, j] == 1)
                {
                    return false;
                }
            }

            for (int i = row - 1, j = col - 1; i > -1 && j > -1; i--, j--)
            {
                if (board[i, j] == 1)
                {
                    return false;
                }
            }

            for (int i = row - 1, j = col + 1; i > -1 && j < board.GetLength(1); i--, j++)
            {
                if (board[i, j] == 1)
                {
                    return false;
                }
            }

            for (int i = row + 1, j = col - 1; j > -1 && i < board.GetLength(0); i++, j--)
            {
                if (board[i, j] == 1)
                {
                    return false;
                }
            }

            return true;
        }

        private static void PrintNQueens(int[,] board)
        {
            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    Console.Write(board[i, j]);
                }

                Console.WriteLine();
            }
        }

        private static void RatMaze()
        {
            int[,] maze = new int[4, 4] {
            {1, 0, 0, 0},
                {1, 1, 0, 1},
                {0, 1, 0, 0},
                {1, 1, 1, 1}
            };

            var solution = new int[4, 4];

            var moves = new Move[2]
            {
                new Move
                {
                    X=1,
                    Y=0
                },new Move
                {
                    X=0,
                    Y=1
                }
            };

            int x = 0, y = 0;
            solution[x, y] = 1;

            if (RatMazeUtil(maze, solution, x, y, moves))
            {
                for (int i = 0; i < solution.GetLength(0); i++)
                {
                    for (int j = 0; j < solution.GetLength(1); j++)
                    {
                        Console.Write(solution[i, j]);
                    }

                    Console.WriteLine();
                }
            }
            else
            {
                Console.WriteLine("no solution");
            }
        }

        private static bool RatMazeUtil(int[,] maze, int[,] solution, int x, int y, Move[] moves)
        {
            var width = maze.GetLength(0);
            var height = maze.GetLength(1);

            if (x == width - 1 && y == height - 1)
            {
                return true;
            }

            foreach (var nextMove in moves)
            {
                var nextX = x + nextMove.X;
                var nextY = y + nextMove.Y;

                if (nextX >= 0 && nextX < width && nextY >= 0 && nextY < height && maze[nextX, nextY] != 0)
                {
                    solution[nextX, nextY] = 1;

                    if (RatMazeUtil(maze, solution, nextX, nextY, moves))
                    {
                        return true;
                    }

                    solution[nextX, nextY] = 0;

                }
            }

            return false;
        }

        private static void KnightsTour()
        {
            int[,] board = new int[8, 8];
            var solutionBoard = new Move[8, 8];

            int i = 0, j = 0;
            board[i, j] = 1;

            int n = 1;

            var moves = GenerateMoves();

            if (KnightsTourUtil(board, i, j, n, moves))
            {
                for (int x = 0; x < 8; x++)
                {
                    for (int y = 0; y < 8; y++)
                    {
                        Console.Write(board[x, y] + " ");
                    }

                    Console.WriteLine();
                }
            }
            else
            {
                Console.WriteLine("No Solution Exists");
            }
        }

        private static Move[] GenerateMoves()
        {
            var moves = new Move[8] 
            {
                new Move{X=1,Y=2},
                new Move{X=-1,Y=2},

                new Move{X=-2,Y=1},
                new Move{X=-2,Y=-1},

                new Move{X=-1,Y=-2},
                new Move{X=1,Y=-2},

                new Move{X=2,Y=1},
                new Move{X=2,Y=-1},
            };
            return moves;
        }

        private static bool KnightsTourUtil(int[,] board, int i, int j, int n, Move[] moves)
        {
            if (n == 64)
            {
                return true;
            }

            foreach (var nextMove in moves)
            {
                if (CheckKnightCanMove(board, nextMove, i, j))
                {
                    n++;
                    var newI = i + nextMove.X;
                    var newJ = j + nextMove.Y;
                    board[newI, newJ] = n;

                    if (KnightsTourUtil(board, newI, newJ, n, moves))
                    {
                        return true;
                    }
                    else
                    {
                        board[newI, newJ] = 0;
                        n--;
                    }
                }
            }

            return false;

        }

        private static bool CheckKnightCanMove(int[,] solution, Move move, int i, int j)
        {
            return move.X + i >= 0 && move.X + i <= 7 &&
                move.Y + j >= 0 && move.Y + j <= 7 &&
                solution[move.X + i, move.Y + j] == 0;
        }


        static string[] FindPermutations(string word)
        {
            if (word.Length == 2)
            {
                char[] _c = word.ToCharArray();
                string s = new string(new char[] { _c[1], _c[0] });
                return new string[]
                {
                    word,
                    s
                };
            }

            List<string> result = new List<string>();

            string[] subsetPermutations = FindPermutations(word.Substring(1));
            char firstChar = word[0];

            foreach (string subest in subsetPermutations)
            {
                string newString = firstChar.ToString() + subest;
                result.Add(newString);
                char[] chars = newString.ToCharArray();

                for (int i = 0; i < newString.Length - 1; i++)
                {
                    char tmp = chars[i];
                    chars[i] = chars[i + 1];
                    chars[i + 1] = tmp;

                    newString = new string(chars);
                    result.Add(newString);
                }
            }

            return result.ToArray();
        }


        private static void Swap(char[] arr, int i, int j)
        {
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = arr[i];
        }

        private static void ExtractTreeLeavesToDLL(Node root, ref LLNode head)
        {
            if (root == null)
            {
                return;
            }

            ExtractTreeLeavesToDLL(root.leftChild, ref head);

            if (root.leftChild == null && root.rightChild == null)//leaf
            {
                if (head == null)
                {
                    head = new LLNode
                    {
                        value = root.item
                    };
                }
                else
                {
                    var newNode = new LLNode
                    {
                        value = root.item
                    };

                    newNode.previous = head;
                    head.next = newNode;

                    head = head.next;
                }
            }

            ExtractTreeLeavesToDLL(root.rightChild, ref head);
        }

        private static LLNode ConvertTreeToDLL(Node root)
        {
            if (root == null)
            {
                return null;
            }

            var head = new LLNode
            {
                value = root.item
            };

            var previous = ConvertTreeToDLL(root.leftChild);
            var next = ConvertTreeToDLL(root.rightChild);

            head.previous = previous;
            if (previous != null)
            {
                previous.next = head;
            }

            head.next = next;
            if (next != null)
            {
                next.previous = head;
            }

            var prev = head.previous;

            while (prev != null)
            {
                head = head.previous;
                prev = head.previous;
            }

            return head;
        }

        private static void nextGreatest(int[] arr)
        {
            Console.WriteLine("nextGreatest");

            var l = arr.Length;

            var greatestFromRight = arr[l - 1];
            arr[l - 1] = -1;

            for (int i = l - 2; i > -1; i--)
            {
                var tmp = arr[i];
                arr[i] = greatestFromRight;

                if (greatestFromRight < tmp)
                {
                    greatestFromRight = tmp;
                }
            }
            for (int i = 0; i < l; i++)
            {
                Console.Write(arr[i] + " ");
            }
            Console.WriteLine("nextGreatest");
        }

        private static void GetKthSmallestNode(Node root, int n)
        {
            if (root == null)
            {
                return;
            }

            GetKthSmallestNode(root.leftChild, n - 1);

            if (n == 0)
            {
                Console.WriteLine(root.item);
                return;
            }

            GetKthSmallestNode(root.rightChild, n - 1);
        }

        private static int GetNodeLevel(Node node, int val, int level)
        {
            if (node == null)
            {
                return -1;
            }

            if (node.item == val)
            {
                return level;
            }

            level++;

            return Math.Max(GetNodeLevel(node.leftChild, val, level),
                GetNodeLevel(node.rightChild, val, level));
        }

        private static bool CheckSumPath(Node root, int n)
        {
            if (root == null)
            {
                if (n == 0)
                {
                    return true;
                }
                else { return false; }
            }

            if (root.leftChild != null && root.rightChild != null)
            {
                if (n - root.item == 0)
                {
                    return true;
                }
            }

            return CheckSumPath(root.leftChild, n - root.item) ||
                CheckSumPath(root.rightChild, n - root.item);
        }

        private static void LevelOrder(Node node)
        {
            var q = new Queue<Node>();
            q.Enqueue(node);

            while (q.Count != 0)
            {
                node = q.Dequeue();
                Console.WriteLine(node.item);

                if (node.leftChild != null)
                {
                    q.Enqueue(node.leftChild);
                }
                if (node.rightChild != null)
                {
                    q.Enqueue(node.rightChild);
                }
            }
        }

        //private static void LevelOrder(Node node)
        //{
        //    int h = GetHeight(node);

        //    for (int i = 0; i < h; i++)
        //    {
        //        PrintLevel(node, i);
        //    }
        //}



        private static void MirrorTree(ref Node root)
        {
            if (root == null)
            {
                return;
            }

            MirrorTree(ref root.leftChild);
            MirrorTree(ref root.rightChild);

            var left = root.leftChild;
            root.leftChild = root.rightChild;
            root.rightChild = left;
        }

        private static void DeleteTree(ref Node node)
        {
            if (node == null)
            {
                return;
            }

            var leftTree = node.leftChild;
            var rightTree = node.rightChild;

            node = null;

            DeleteTree(ref leftTree);
            DeleteTree(ref rightTree);
        }

        private static int CalculateTreeSize(Node root)
        {
            if (root == null)
            {
                return 0;
            }

            return 1 + CalculateTreeSize(root.leftChild) + CalculateTreeSize(root.rightChild);
        }

        private static void MergeTwoLLAlternatively(LLNode l1, LLNode l2)
        {
            while (l1 != null && l2 != null)
            {
                var tmpl1 = l1.next;
                var tmpl2 = l2.next;

                l1.next = l2;
                l2.next = tmpl1;

                l1 = tmpl1;
                l2 = tmpl2;
            }
        }

        private static void InsertIntoSortedLL(LLNode head, int val)
        {
            if (head == null)
            {
                head = new LLNode { value = val };
                //return head;
            }
            else if (val < head.value)
            {
                var newNode = new LLNode { value = val };
                newNode.next = head;
                //return newNode;
            }

            var faster = head.next;

            while (faster.value < val && faster != null)
            {
                head = head.next;
                faster = faster.next;
            }

            head.next = new LLNode { value = val, next = faster };
            //return head;
        }

        private static bool CheckPalindrome(LLNode head)
        {
            Console.WriteLine("CheckPalindromeRecursive");
            return CheckPalindromeRecursive(ref head, head);
        }

        private static bool CheckPalindromeRecursive(ref LLNode left, LLNode right)
        {
            if (right == null)
            {
                return true;
            }

            if (CheckPalindromeRecursive(ref left, right.next))
            {
                if (left.value == right.value)
                {
                    left = left.next;
                    return true;
                }
            }

            return false;
        }

        //private static bool CheckPalindromeRecursive(ref LLNode left, LLNode right)
        //{
        //    if (right == null)
        //    {
        //        return true;
        //    }

        //    bool isPal = CheckPalindromeRecursive(ref left, right.next);

        //    if (!isPal)
        //    {
        //        return false;
        //    }

        //    isPal = left.value == right.value;
        //    left = left.next;

        //    return isPal;
        //}

        private static LLNode ReverseLinkedList(LLNode head)
        {
            LLNode prev = null;

            while (head != null)
            {
                var nxt = head.next;
                head.next = prev;
                prev = head;
                head = nxt;
            }

            return prev;
        }

        private static void DeleteLinkedList(ref LLNode head)
        {
            while (head != null)
            {
                var tmp = head.next;
                head = null;
                head = tmp;
            }
        }

        private static void GetNthFromEnd(LLNode head, int n)
        {
            var fast = head;

            for (int i = 0; i < n; i++)
            {
                if (fast != null)
                {
                    fast = fast.next;
                }
            }

            if (fast == null)
            {
                Console.WriteLine("No"); return;
            }

            while (fast != null)
            {
                head = head.next;
                fast = fast.next;
            }
            Console.WriteLine(head.value);
        }

        private static void DeleteNode(LLNode node)
        {
            var nxtNode = node.next;
            node.value = nxtNode.value;
            node.next = nxtNode.next;
        }

        private static void GetNth(LLNode head, int idx)
        {
            int count = 1;

            while (head != null)
            {
                if (count == idx)
                {
                    Console.WriteLine(head.value);
                    return;
                }

                head = head.next;
                count++;
            }

            if (count != idx)
            {
                Console.WriteLine("our of range");
            }
        }

        private static void MedianTwoSortedArrays(int[] arr1, int[] arr2)
        {
            int m1 = 0, m2;

            int i = 0, j = 0;
            int count = 0;

            while (count < arr1.Length)
            {
                if (arr1[i] == arr2[j])
                {
                    m1 = arr1[i];
                    i++;
                    j++;
                }
                else if (arr1[i] < arr2[j])
                {
                    m1 = arr1[i];
                    i++;
                }
                else
                {
                    m1 = arr2[j];
                    j++;
                }

                count++;
            }
            if (i < arr1.Length && j < arr2.Length)
            {
                if (arr1[i] < arr2[j])
                {
                    m2 = arr1[i];
                }
                else
                {
                    m2 = arr2[j];
                }
            }
            else if (i < arr1.Length)
            {
                m2 = arr1[i];
            }
            else
            {
                m2 = arr2[j];
            }

            Console.WriteLine((m1 + m2) / 2);
        }

        private static void RotateArray(int[] arr, int d)
        {
            var tmp = new int[d];

            for (int j = 0; j < d; j++)
            {
                tmp[j] = arr[j];
            }

            int i = 0;
            for (; i < arr.Length - d; i++)
            {
                arr[i] = arr[i + d];
            }
            for (int j = 0; j < d; j++)
            {
                arr[i] = tmp[j];
                i++;
            }

            foreach (var item in arr)
            {
                Console.Write(item);
            }
        }

        private static void Leaders(int[] arr)
        {
            var leader = arr[arr.Length - 1];
            Console.WriteLine(leader);

            for (int i = arr.Length - 2; i > -1; i--)
            {
                if (arr[i] > leader)
                {
                    Console.WriteLine(arr[i]);
                    leader = arr[i];
                }
            }
        }

        private static void ArraysIntersection(int[] arr1, int[] arr2)
        {
            int i = 0;
            int j = 0;

            while (i < arr1.Length && j < arr2.Length)
            {
                if (arr1[i] == arr2[j])
                {
                    Console.WriteLine(arr1[i]);
                    i++;
                    j++;
                }
                else if (arr1[i] < arr2[j])
                {
                    i++;
                }
                else { j++; }
            }
        }

        private static void ArraysUnion(int[] arr1, int[] arr2)
        {
            int i = 0;
            int j = 0;

            while (i < arr1.Length && j < arr2.Length)
            {
                if (arr1[i] == arr2[j])
                {
                    Console.WriteLine(arr2[j]);
                    i++;
                    j++;
                }
                else if (arr1[i] < arr2[j])
                {
                    Console.WriteLine(arr1[i]);
                    i++;
                }
                else
                {
                    Console.WriteLine(arr2[j]);
                    j++;
                }
            }

            for (; i < arr1.Length; i++)
            {
                Console.WriteLine(arr1[i]);
            }
            for (; j < arr2.Length; i++)
            {
                Console.WriteLine(arr2[j]);
            }
        }

        private static void MaxDifference(int[] arr)
        {
            var min = arr[0];
            var maxDiff = arr[1] - min;

            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] - min > maxDiff)
                {
                    maxDiff = arr[i] - min;
                }
                if (arr[i] < min)
                {
                    min = arr[i];
                }
            }

            Console.WriteLine(maxDiff);
        }

        private static void CountSmaller(int[] arr)
        {
            var smaller = new int[arr.Length];
            var count = 0;
            smaller[arr.Length - 1] = 0;
            var min = arr[arr.Length - 1];

            for (int i = arr.Length - 2; i > -1; i--)
            {
                if (arr[i] > min)
                {
                    smaller[i] = count;
                }
                else
                {
                    min = arr[i];
                    count++;
                }
            }

            foreach (var item in smaller)
            {
                Console.Write(item);
            }
        }

        private static void SortedSequenceOfSize3(int[] arr)
        {
            var smaller = new int[arr.Length];
            var minValue = arr[0];
            smaller[0] = -1;

            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] < minValue)
                {
                    minValue = arr[i];
                    smaller[i] = -1;
                }
                else
                {
                    smaller[i] = minValue;
                }
            }

            var greater = new int[arr.Length];
            minValue = arr[arr.Length - 1];
            greater[arr.Length - 1] = -1;

            for (int i = arr.Length - 2; i > -1; i--)
            {
                if (arr[i] > minValue)
                {
                    minValue = arr[i];
                    greater[i] = -1;
                }
                else
                {
                    greater[i] = minValue;
                }
            }

            for (int i = 0; i < arr.Length; i++)
            {
                if (smaller[i] != -1 && greater[i] != -1)
                {
                    Console.Write(smaller[i]);
                    Console.Write(arr[i]);
                    Console.WriteLine(greater[i]);
                }
            }

        }

        private static void RearrangeNegativeAndPositive(int[] arr)
        {
            int pos = 0;

            for (int neg = 0; neg < arr.Length; neg++)
            {
                if (arr[neg] < 0)
                {
                    Swap(arr, pos, neg);
                    pos++;
                }
            }
        }

        private static int MinimumInRotatedSortedArray(int[] arr, int start, int end)
        {
            int mid = (start + end) / 2;

            if (mid != start && arr[mid] >= arr[start])//not rotated
            {
                return arr[0];
            }
            if (mid != 0 && arr[mid] < arr[mid - 1])
            {
                return arr[mid];
            }
            if (arr[mid] < arr[start])
            {
                return MinimumInRotatedSortedArray(arr, start, mid - 1);
            }
            else
            {
                return MinimumInRotatedSortedArray(arr, mid + 1, end);
            }
        }

        private static void SizeOfLargestBSTSubtree(Node node, ref int totalSize, ref int sizeSoFar)
        {
            if (node != null && node.leftChild != null && node.rightChild != null)
            {
                if (node.leftChild.item <= node.item && node.rightChild.item > node.item)
                {
                    sizeSoFar += sizeSoFar == 0 ? 3 : 2;
                }
                else
                {
                    sizeSoFar = 0;
                }


                if (sizeSoFar > totalSize)
                {
                    totalSize = sizeSoFar;
                }

                SizeOfLargestBSTSubtree(node.leftChild, ref totalSize, ref sizeSoFar);
                SizeOfLargestBSTSubtree(node.rightChild, ref totalSize, ref sizeSoFar);
            }
        }

        private static void PopulateInorderSuccessor(Node root, ref Node next)
        {
            if (root == null)
            {
                return;
            }

            PopulateInorderSuccessor(root.rightChild, ref next);
            root.NextRight = next;
            next = root;
            PopulateInorderSuccessor(root.leftChild, ref next);
        }

        private static void ConnectNodesAtSameLevel(Node root)
        {
            root.NextRight = null;
            ConnectNodesRecursive(root);
        }

        private static void ConnectNodesRecursive(Node root)
        {
            if (root == null)
            {
                return;
            }

            if (root.leftChild != null)
            {
                if (root.rightChild != null)
                {
                    root.leftChild.NextRight = root.rightChild;
                    root.rightChild.NextRight = GetNextRight(root);
                }
                else
                {
                    root.leftChild.NextRight = GetNextRight(root);
                }
            }
            if (root.rightChild != null)
            {
                root.rightChild.NextRight = GetNextRight(root);
            }
            ConnectNodesRecursive(root.leftChild);
            ConnectNodesRecursive(root.rightChild);
        }

        private static Node GetNextRight(Node root)
        {
            var nextRight = root.NextRight;

            while (nextRight != null)
            {
                if (nextRight.leftChild != null)
                {
                    return nextRight.leftChild;
                }
                if (nextRight.rightChild != null)
                {
                    return nextRight.rightChild;
                }

                nextRight = nextRight.NextRight;
            }
            return null;
        }

        private static void BreadthTraversalUsingQueue(Node node)
        {
            var q = new Queue<Node>();

            while (node != null)
            {
                Console.WriteLine(node.item);

                if (node.leftChild != null)
                {
                    q.Enqueue(node.leftChild);
                }
                if (node.rightChild != null)
                {
                    q.Enqueue(node.rightChild);
                }

                if (q.Count == 0)
                {
                    node = null;
                }
                else
                {
                    node = q.Dequeue();
                }
            }
        }

        private static bool CheckIsSubSet(Node bigTree, Node smallTree)
        {
            if (smallTree == null)
            {
                return true;
            }
            if (bigTree == null)
            {
                return false;
            }
            if (CheckTreesAreIdentical(bigTree, smallTree))
            {
                return true;
            }

            return CheckTreesAreIdentical(bigTree.leftChild, smallTree) || CheckTreesAreIdentical(bigTree.rightChild, smallTree);
        }

        private static bool CheckTreesAreIdentical(Node bigTree, Node smallTree)
        {
            if (bigTree == null && smallTree == null)
            {
                return true;
            }
            if (bigTree == null || smallTree == null)
            {
                return false;
            }
            return bigTree.item == smallTree.item &&
                CheckTreesAreIdentical(bigTree.leftChild, smallTree.leftChild) &&
                CheckTreesAreIdentical(bigTree.rightChild, smallTree.rightChild);
        }



        private static bool CheckIsSumTree(Node node)
        {
            if (node == null || (node.leftChild == null && node.rightChild == null))
            {
                return true;
            }

            int left = GetSum(node.leftChild);
            int right = GetSum(node.rightChild);

            if (node.item == left + right)
            {
                if (CheckIsSumTree(node.leftChild) && CheckIsSumTree(node.rightChild))
                {
                    return true;
                }
            }

            return false;

        }

        private static int GetSum(Node node)
        {
            if (node == null)
            {
                return 0;
            }

            return node.item + GetSum(node.leftChild) + GetSum(node.rightChild);
        }

        private static void PrintAncestorsOfNode(Node root, int p, List<Node> list)
        {
            if (root == null)
            {
                return;
            }

            if (root.item == p)
            {
                list.ForEach(x => Console.WriteLine(x.item));
            }
            else
            {
                list.Add(root);
                PrintAncestorsOfNode(root.leftChild, p, list);
                PrintAncestorsOfNode(root.rightChild, p, list);
            }
            if (list.Any())
            {
                list.RemoveAt(list.Count - 1);
            }
        }

        private static int FindKSmallestElement(Node root, int n)
        {
            Stack<Node> s = new Stack<Node>();
            s.Push(root);
            root = root.leftChild;

            while (true)
            {
                if (root != null)
                {
                    s.Push(root);
                    root = root.leftChild;
                }
                else
                {
                    if (s.Count != 0)
                    {
                        var node = s.Pop();
                        n--;
                        if (n == 0)
                        {
                            return node.item;
                        }
                        root = node.rightChild;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            return 0;
        }

        private static void PrintNodesAtKDistanceFromRoot(Node root, int n)
        {
            if (root == null)
            {
                return;
            }

            if (n == 0)
            {
                Console.WriteLine(root.item);
            }
            else
            {
                PrintNodesAtKDistanceFromRoot(root.leftChild, n - 1);
                PrintNodesAtKDistanceFromRoot(root.rightChild, n - 1);
            }
        }



        private static void InOrderTraversalWithoutRecursion(Node root)
        {
            if (root == null)
            {
                return;
            }

            var stack = new Stack<Node>();

            while (true)
            {
                if (root != null)
                {
                    stack.Push(root);
                    root = root.leftChild;
                }
                else
                {
                    if (stack.Count != 0)
                    {
                        root = stack.Pop();
                        Console.Write(root.item);
                        root = root.rightChild;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        private static void ConvertTreeToChildrenSum(Node root)
        {
            if (root == null || root.rightChild == null || root.leftChild == null)
            {
                return;
            }
            ConvertTreeToChildrenSum(root.leftChild);
            ConvertTreeToChildrenSum(root.rightChild);
            int sum = (root.leftChild == null ? 0 : root.leftChild.item) + (root.rightChild == null ? 0 : root.rightChild.item);
            int diff = sum - root.item;

            if (diff > 0)
            {
                root.item += diff;
            }
            if (diff < 0)
            {
                IncrementNodeChildren(root, -diff);
            }
        }

        private static void IncrementNodeChildren(Node root, int diff)
        {
            if (root.leftChild != null)
            {
                root.leftChild.item += diff;
                IncrementNodeChildren(root.leftChild, diff);
            }
            else if (root.rightChild != null)
            {
                root.rightChild.item += diff;
                IncrementNodeChildren(root.rightChild, diff);
            }
        }

        private static int CountLeafNodes(Node node)
        {
            if (node == null)
            {
                return 0;
            }

            if (node.leftChild == null && node.rightChild == null)
            {
                return 1;
            }

            return CountLeafNodes(node.leftChild) + CountLeafNodes(node.rightChild);
        }

        private static Node FindLowestCommonAncestor(Node root, int a, int b)
        {
            if (Math.Max(a, b) < root.item)
            {
                return FindLowestCommonAncestor(root.leftChild, a, b);
            }
            if (Math.Min(a, b) > root.item)
            {
                return FindLowestCommonAncestor(root.rightChild, a, b);
            }

            return root;
        }

        private static void PrintAllPathsFromRootToLeaf(Node node, List<Node> lst)
        {
            if (node == null)
            {
                return;
            }

            lst.Add(node);

            if (node.leftChild == null && node.rightChild == null && lst.Any())
            {
                foreach (var item in lst)
                {
                    Console.Write(item.item);
                }

                Console.WriteLine();
            }
            else
            {
                PrintAllPathsFromRootToLeaf(node.leftChild, lst);
                PrintAllPathsFromRootToLeaf(node.rightChild, lst);
            }

            lst.RemoveAt(lst.Count - 1);
        }



        private static int GetTreeHeight(Node node)
        {
            if (node == null)
            {
                return 0;
            }

            return 1 + Math.Max(GetTreeHeight(node.leftChild), GetTreeHeight(node.rightChild));
        }

        private static bool TreesAreEqual(Node node1, Node node2)
        {
            if (node1 == null && node2 == null)
            {
                return true;
            }
            if (node1 != null && node2 != null)
            {
                if (node1.item == node2.item)
                {
                    return TreesAreEqual(node1.leftChild, node2.leftChild) && TreesAreEqual(node1.rightChild, node2.rightChild);
                }
            }

            return false;
        }

        private static int GetTreeSize(Node node)
        {
            if (node == null)
            {
                return 0;
            }

            else return 1 + GetTreeSize(node.leftChild) + GetTreeSize(node.rightChild);
        }

        private static void ConvertTreeToLinkedList(Node node, ref LLNode headTree)
        {
            if (node == null)
            {
                return;
            }

            ConvertTreeToLinkedList(node.leftChild, ref headTree);

            if (headTree == null)
            {
                headTree = new LLNode { value = node.item };
            }
            else
            {
                var tmpNode = new LLNode { value = node.item };

                tmpNode.previous = headTree;
                headTree.next = tmpNode;

                headTree = headTree.next;
            }


            ConvertTreeToLinkedList(node.rightChild, ref headTree);
        }

        private static LLNodeRandom CopyRandomLinkedList(LLNodeRandom head)
        {
            LLNodeRandom copy = new LLNodeRandom { Value = head.Value };
            copy.Random = head;

            LLNodeRandom tmpHead = copy;
            var navigation = head.Next;
            head.Next = copy;

            while (navigation != null)
            {
                tmpHead.Next = new LLNodeRandom { Value = navigation.Value };
                tmpHead = tmpHead.Next;

                var tmpNext = navigation.Next;
                navigation.Next = tmpHead;
                tmpHead.Random = navigation;

                navigation = tmpNext;
            }

            return copy;
        }

        private static LLNode RemoveDuplicates(LLNode head)
        {
            LLNode res = head;
            LLNode next = head.next;

            while (head != null)
            {
                LLNode prev = head;
                next = head.next;

                while (next != null)
                {
                    var tmpAfter = next.next;

                    if (head.value == next.value)
                    {
                        prev.next = tmpAfter;
                        next = null;
                    }

                    prev = next;
                    next = tmpAfter;
                }

                head = head.next;
            }

            return res;
        }

        private static void ReverseDoublyLinkedList(ref LLNode current)
        {
            var prev = current.previous;

            while (current != null)
            {
                prev = current.previous;
                var next = current.next;

                current.next = prev;
                current.previous = next;

                prev = current;
                current = next;
            }

            current = prev;
        }

        private static void SplitCircularLinkedList(LLNode head, ref LLNode a, ref LLNode b)
        {
            var slow = head;
            var fast = head.next;
            a = head;

            while (fast != null && fast.next != head)
            {
                slow = slow.next;
                fast = fast.next.next;
            }
            slow = slow.next;

            var tmpHead = head.next;
            while (tmpHead != slow)
            {
                a.next = tmpHead;
                a = a.next;
                tmpHead = tmpHead.next;
            }
            a.next = head;
            a = a.next;

            b = slow;
            var tmpSlow = slow.next;
            while (tmpSlow != head)
            {
                b.next = tmpSlow;
                b = b.next;
                tmpSlow = tmpSlow.next;
            }
            b.next = slow;
            b = b.next;
        }

        private static LLNode PairwiseSwap(LLNode head)
        {
            var current = head;
            var next = head.next;

            while (current != null && current.next != null && next != null && next.next != null)
            {
                var tmp = current.value;
                current.value = next.value;
                next.value = tmp;

                current = current.next.next;
                next = next.next.next;
            }

            return head;
        }

        private static LLNode DeleteAlternate(LLNode head)
        {
            var current = head;
            var next = head.next;

            while (next != null && next.next != null)
            {
                current.next = next.next;
                current = current.next;
                next = next.next.next;
            }

            return head;
        }

        private static void AlternatingSplit(ref LLNode a, ref LLNode b, LLNode head)
        {
            var current = head;
            var next = head.next;

            a = current;
            b = next;

            while (current != null && current.next != null && next != null && next.next != null)
            {
                current.next = current.next.next;
                current = current.next;
                next.next = next.next.next;
                next = next.next;
            }
        }

        private static LLNode InsertInCircularLinkedList(LLNode head, int value)
        {
            var newNode = new LLNode { value = value };

            if (value < head.value)
            {
                newNode.next = head;

                var tmpHead = head;

                while (tmpHead.next != head)
                {
                    tmpHead = tmpHead.next;
                }

                tmpHead.next = newNode;

                return newNode;
            }


            LLNode prev = head;
            LLNode current = head.next;

            while (current != null && current != head && current.value < value)
            {
                prev = prev.next;
                current = current.next;
            }

            var tmpNext = prev.next;
            prev.next = newNode;
            newNode.next = tmpNext;

            return head;
        }

        private static void DeleteNodesWithGreaterValueOnrightSide(ref LLNode head)
        {
            var tmp = head;

            while (tmp != null)
            {
                if (tmp.next != null && tmp.value < tmp.next.value)
                {
                    DeleteNode(tmp);
                }

                tmp = tmp.next;
            }
        }

        private static void DeleteFirstNode(ref LLNode head)
        {
            var next = head.next;
            head = null;
            head = next;
        }

        private static Node MakeTreeFromLinkedList(LLNode node)
        {
            if (node == null)
            {
                return null;
            }

            LLNode middle = GetMiddle(node);
            if (middle == null)
            {
                return null;
            }
            Node result = new Node { item = middle.value };
            result.leftChild = MakeTreeFromLinkedList(node);
            result.rightChild = MakeTreeFromLinkedList(middle);
            return result;
        }

        private static void MergeSortLinkedList(ref LLNode node)
        {
            if (node == null || node.next == null)
            {
                return;
            }

            LLNode middle = GetMiddle(node);
            MergeSortLinkedList(ref node);
            MergeSortLinkedList(ref middle);

            node = Merge(node, middle);
        }

        private static LLNode GetMiddle(LLNode node)
        {
            LLNode slow = node;
            LLNode fast = node.next;

            while (fast != null)
            {
                fast = fast.next;

                if (fast != null)
                {
                    slow = slow.next;
                    fast = fast.next;
                }
            }
            var tmp = slow.next;
            slow.next = null;
            return tmp;
        }

        private static LLNode RotateLinkedListAtK(LLNode head, int k)
        {
            var firsthead = head;

            for (int i = 0; i < k - 1; i++)
            {
                head = head.next;
            }

            var secondHead = head.next;
            var tmp2 = head.next;
            head.next = null;

            while (tmp2.next != null)
            {
                tmp2 = tmp2.next;
            }

            tmp2.next = firsthead;
            return secondHead;
        }

        private static LLNode RotateLinkedListByK(LLNode head, int k)
        {
            LLNode result = head;

            for (int i = 0; i < k; i++)
            {
                result = RotateByOne(result, result);
            }

            return result;
        }

        private static LLNode RotateByOne(LLNode head, LLNode beforeLast)
        {
            if (beforeLast != null && beforeLast.next != null)
            {
                LLNode last = beforeLast.next;

                if (last.next == null)
                {
                    beforeLast.next = null;
                    last.next = head;
                    return last;
                }
            }

            beforeLast = beforeLast.next;
            return RotateByOne(head, beforeLast);
        }

        private static LLNode FlatteningLinkedList(LLNode head)
        {
            LLNode result = null;

            while (head != null)
            {
                var tmpResult = Merge(head, head.next);
                result = Merge(result, tmpResult);

                if (head.next != null)
                {
                    head = head.next.next;
                }
                else
                {
                    return result;
                }
            }

            return result;
        }

        private static LLNode Merge(LLNode a, LLNode b)
        {
            if (a == null)
            {
                return b;
            }
            if (b == null)
            {
                return a;
            }

            LLNode result;

            if (a.value < b.value)
            {
                result = a;
                result.next = Merge(a.next, b);
            }
            else
            {
                result = b;
                result.next = Merge(b.next, a);
            }

            return result;
        }

        private static LLNode SumLinkedListMostSignificant(LLNode first, LLNode second, ref int carry)
        {
            LLNode result = new LLNode();

            if ((first != null && first.next != null) || (second != null && second.next != null))
            {
                var dummyNode = new LLNode { value = 0 };
                result.next = SumLinkedListMostSignificant(first.next ?? dummyNode, second.next ?? dummyNode, ref carry);
            }

            result.value = CreateResultNode(first, second, ref carry).value;
            return result;
        }

        private static LLNode SumLinkedListLeastSignificant(LLNode first, LLNode second, ref int carry)
        {
            LLNode head = null, current = null;

            while (first != null || second != null)
            {
                var newNode = CreateResultNode(first, second, ref carry);

                if (head == null)
                {
                    head = newNode;
                    current = head;
                }
                else
                {
                    current.next = newNode;
                    current = current.next;
                }

                if (first != null)
                {
                    first = first.next;
                }

                if (second != null)
                {
                    second = second.next;
                }
            }

            return head;
        }

        private static LLNode CreateResultNode(LLNode first, LLNode second, ref int carry)
        {
            int sum = carry + (first == null ? 0 : first.value) + (second == null ? 0 : second.value);

            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum % 10 : sum; ;

            var newNode = new LLNode { value = sum };
            return newNode;
        }



        private static LLNode FindLoopInLinkedList(LLNode head)
        {
            var slow = head;
            var fast = head.next;

            while (slow != null)
            {
                if (slow == fast)
                {
                    return slow;
                }

                slow = slow.next;
                if (fast.next != null)
                {
                    fast = fast.next.next;
                }
            }

            return null;
        }





        private static LLNode CopyLinkedList(LLNode head)
        {
            LLNode res = head;
            LLNode head2 = head;

            while (head != null)
            {
                res = head;
                head = head.next;
            }

            return head2;
        }



        private static int GetHeightUsingStack(Node node)
        {
            Stack<Node> nodes = new Stack<Node>();
            nodes.Push(node);
            int count = 0;
            while (nodes.Count != 0)
            {
                var tmp = nodes.Pop();

                if (tmp != null)
                {

                }
            }

            return count;
        }

        private static Node BuildTree(LLNode head, int n)
        {
            if (n == 0)
            {
                return null;
            }

            n /= 2;
            Node root = new Node();
            var tmpNode = head;
            for (int i = 0; i < n; i++)
            {
                if (tmpNode.next != null)
                {
                    tmpNode = tmpNode.next;
                }
            }
            root.item = tmpNode.value;

            root.leftChild = BuildTree(head, n);
            root.rightChild = BuildTree(tmpNode.next, n);

            return root;
        }

        private static Node BuildTree(int[] array, int start, int end)
        {
            if (start >= end)
            {
                return null;
            }

            int middle = (start + end) / 2;
            Node n = new Node { item = array[middle] };
            n.leftChild = BuildTree(array, 0, middle);
            n.rightChild = BuildTree(array, middle, end);
            return n;
        }

        private static int CountImpl<T>(ICollection<T> collection)
        {
            Console.WriteLine("ICollection<T>");
            return collection.Count;
        }

        private static int CountImpl(ICollection collection)
        {
            return collection.Count;
        }

        private static int CountImpl(string text)
        {
            return text.Length;
        }

        private static int CountImpl(IEnumerable collection)
        {
            Console.WriteLine("IEnumerable");
            int count = 0;
            foreach (object item in collection)
            {
                count++;
            }
            return count;
        }

        public static void PrintCount(IEnumerable collection)
        {
            dynamic d = collection;
            int count = CountImpl(d);
            Console.WriteLine(count);
        }

        private static void InOrderTraversal(Node node)
        {
            if (node == null)
            {
                return;
            }
            Console.WriteLine(node.item);
            InOrderTraversal(node.leftChild);
            InOrderTraversal(node.rightChild);
        }

        static IEnumerable<int> foo()
        {
            bool ff = true;
            int i = 0;
            while (ff)
            {
                yield return i++;
            }
        }

        //static void nextGreatest(int[] arr, int size)
        //{
        //    // Initialize the next greatest element 
        //    int max_from_right = arr[size - 1];

        //    // The next greatest element for the rightmost element
        //    // is always -1
        //    arr[size - 1] = -1;

        //    // Replace all other elements with the next greatest
        //    for (int i = size - 2; i >= 0; i--)
        //    {
        //        // Store the current element (needed later for updating
        //        // the next greatest element)
        //        int temp = arr[i];

        //        // Replace current element with the next greatest
        //        arr[i] = max_from_right;

        //        // Update the greatest element, if needed
        //        if (max_from_right < temp)
        //            max_from_right = temp;
        //    }
        //}

        private static bool CheckIsBST(Node node, int min, int max)
        {
            if (min > node.item || max < node.item)
            {
                return false;
            }

            bool left = true;
            if (node.leftChild != null)
            {
                left = CheckIsBST(node.leftChild, min, max - 1);
            }

            bool right = true;
            if (node.rightChild != null)
            {
                right = CheckIsBST(node.rightChild, min + 1, max);
            }

            return left && right;
        }

        private static int GetMax(Node node)
        {
            if (node.leftChild == null && node.rightChild == null)
            {
                return node.item;
            }

            var left = GetMax(node.leftChild);
            var right = GetMax(node.rightChild);
            return Math.Max(left, right);
        }

        private static int GetMin(Node node)
        {
            if (node.leftChild == null && node.rightChild == null)
            {
                return node.item;
            }

            int l = int.MaxValue;
            if (node.leftChild != null)
            {
                l = GetMin(node.leftChild);
            }
            int r = int.MaxValue;
            if (node.rightChild != null)
            {
                r = GetMin(node.rightChild);
            }

            if (l > r)
            {
                return r;
            }
            else
            {
                return l;
            }
        }

        private static void swap(int[] a, int first, int second)
        {

            int temp;

            temp = a[first];

            a[first] = a[second];

            a[second] = temp;

        }

        private static void arrange(int[] a, int size)
        {

            int zero = 0, one = 0, two = size - 1;

            while (one <= two)
            {

                switch (a[one])
                {

                    case 0:

                        swap(a, zero, one);

                        zero++;

                        one++;

                        break;

                    case 1:

                        one++;

                        break;

                    case 2:

                        swap(a, one, two);

                        two--;

                        break;



                }

            }

        }

        private static void BreadthTraversal(Node tree)
        {
            bool ltr = true;
            int treeHeight = GetHeight(tree);
            for (int i = 0; i < treeHeight; i++)
            {
                PrintLevel(tree, i + 1, ltr);

                Console.WriteLine();
                //ltr = !ltr;
            }
        }

        private static int GetHeight(Node tree)
        {
            if (tree == null)
            {
                return 0;
            }

            return 1 + Math.Max(GetHeight(tree.leftChild), GetHeight(tree.rightChild));
        }

        private static void PrintLevel(Node node, int lvl)
        {
            if (node == null)
            {
                return;
            }
            if (lvl == 0)
            {
                Console.WriteLine(node.item);
            }

            PrintLevel(node.leftChild, lvl - 1);
            PrintLevel(node.rightChild, lvl - 1);
        }

        private static void PrintLevel(Node node, int lvl, bool ltr)
        {
            if (node == null)
            {
                return;
            }
            if (lvl == 1)
            {
                Console.Write(node.item + " ");
            }
            else
            {
                if (ltr)
                {
                    PrintLevel(node.leftChild, lvl - 1, ltr);
                    PrintLevel(node.rightChild, lvl - 1, ltr);
                }
                else
                {
                    PrintLevel(node.rightChild, lvl - 1, ltr);
                    PrintLevel(node.leftChild, lvl - 1, ltr);
                }
            }
        }

        private static Node LCA(Node root, Node p, Node q)
        {
            if (root == null)
            {
                return null;
            }
            if (root == p || root == q)
            {
                return root;
            }
            Node L = LCA(root.leftChild, p, q);
            Node R = LCA(root.rightChild, p, q);
            if (L != null && R != null)
            {
                return root;  // if p and q are on both sides
            }
            return L != null ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees


            //            Node *LCA(Node *root, Node *p, Node *q) {
            //  if (!root || !p || !q) return NULL;
            //  if (max(p->data, q->data) < root->data)
            //    return LCA(root->left, p, q);
            //  else if (min(p->data, q->data) > root->data)
            //    return LCA(root->right, p, q);
            //  else
            //    return root;
            //}

        }

        private static Node GetParent(Node root, Node n, int rank)
        {
            if (root.leftChild == n || root.rightChild == n)
            {
                return root;
            }
            else
            {
                if (root.leftChild != null)
                {
                    rank++;
                    return GetParent(root.leftChild, n, rank);
                }
                if (root.rightChild != null)
                {
                    rank++;
                    return GetParent(root.rightChild, n, rank);
                }
                return n;
            }

        }

        private static LLNode ReverseAlternateNodesLinkedList(LLNode head, int k)
        {
            var tmpHead = head;
            LLNode next = null;
            int i = 0;
            LLNode prev = null;

            while (tmpHead != null && i < k)
            {
                next = tmpHead.next;
                tmpHead.next = prev;
                prev = tmpHead;
                tmpHead = next;
                i++;
            }

            i = 0;

            while (head != null && i < k)
            {
                head.next = next;
                head = head.next;
                if (next != null)
                {
                    next = next.next;
                }
                i++;
            }

            if (next != null)
            {
                head.next = ReverseAlternateNodesLinkedList(next, k);
            }

            return prev;
        }

        private static void PrintLL(LLNode n)
        {
            while (n != null)
            {
                Console.Write(n.value + " ");
                n = n.next;
            }
            Console.WriteLine();
        }

        private static void BoundaryTraversal(Node node)
        {
            Console.WriteLine(node.item);
            PrintLeftNodes(node.leftChild);
            PrintLeaves(node);
            PrintRightNodes(node.rightChild);
        }

        private static void PrintRightNodes(Node node)
        {
            if (node.rightChild != null)
            {
                PrintRightNodes(node.rightChild);
            }
            if (!CheckIsLeaf(node))
            {
                Console.WriteLine(node.item);
            }
        }

        private static void PrintLeftNodes(Node node)
        {
            while (node != null)
            {
                if (node.leftChild != null || node.rightChild != null)
                {
                    Console.WriteLine(node.item);
                }
                node = node.leftChild;
            }
        }

        private static void PrintLeaves(Node node)
        {
            if (node != null)
            {
                if (CheckIsLeaf(node))
                {
                    Console.WriteLine(node.item);
                }
                else
                {
                    PrintLeaves(node.leftChild);
                    PrintLeaves(node.rightChild);
                }
            }
        }

        private static bool CheckIsLeaf(Node node)
        {
            return node.leftChild == null && node.rightChild == null;
        }

        private static IEnumerable<int> GetLIS(int[] arr)
        {
            List<List<int>> res = new List<List<int>>();

            for (int i = 0; i < arr.Length - 1; i++)
            {
                var innerList = new List<int>();
                innerList.Add(arr[i]);

                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (innerList[innerList.Count - 1] <= arr[j])
                    {
                        innerList.Add(arr[j]);
                    }
                }

                res.Add(innerList);
            }

            int maxIdx = 0;
            int maxLIS = res[maxIdx].Count;

            for (int i = 1; i < res.Count; i++)
            {
                if (maxLIS < res[i].Count)
                {
                    maxIdx = i;
                }
            }

            return res[maxIdx];
        }

        private static void GetCombinations(string str)
        {
            var n = Math.Pow(2, str.Length);
            for (int i = 0; i < n; i++)
            {
                string binary = Convert.ToString(i, 2);
                var token = binary.PadLeft(str.Length, '0');
                for (int j = 0; j < token.Length; j++)
                {
                    if (token[j] != '0')
                    {
                        Console.Write(str[j]);
                    }
                }
                Console.WriteLine();
            }
        }

        static List<string> GetCombinations(string inputStr, int index)
        {
            var newCombinations = new List<string>();
            if (index == inputStr.Length - 1)
            {
                newCombinations.Add(inputStr.Substring(index));
            }
            else
            {
                var combinations = GetCombinations(inputStr, index + 1);
                foreach (string str in combinations)
                {
                    newCombinations.Add(str);
                    newCombinations.Add(inputStr[index].ToString() + str);
                }
                newCombinations.Add(inputStr[index].ToString());
            }
            return newCombinations;
        }

        private static void CountSort(int[] a, int largestNumber)
        {
            int[] countArr = new int[largestNumber + 1];

            foreach (var item in a)
            {
                countArr[item]++;
            }

            for (int i = 0; i < countArr.Length; i++)
            {
                for (int j = 0; j < countArr[i]; j++)
                {
                    Console.WriteLine(i);
                }
            }
        }

        private static void QuickSelect(int[] a, int left, int right, int k, List<int> arr)
        {
            int i = left;
            int j = right;
            int pivotindex = (left + right) / 2;
            int pivotvalue = a[pivotindex];

            while (i <= j)
            {
                while (a[i] < pivotvalue && i < right)
                {
                    i++;
                }
                while (a[j] > pivotvalue && j > left)
                {
                    j--;
                }

                if (i <= j)
                {
                    Swap(a, i, j);
                    i++;
                    j--;
                }
            }

            int greatersize = a.Length - (pivotindex + 1);

            if (k < greatersize)
            {
                QuickSelect(a, pivotindex + 1, right, k, arr);
            }
            else if (k == greatersize)
            {
                for (int m = pivotindex + 1; m <= right; m++)
                {
                    arr.Add(a[m]);
                }
            }
            else
            {
                if (k == (greatersize + 1))
                {
                    for (int m = i; m < j; m++)
                    {
                        arr.Add(a[m]);
                    }
                    arr.Add(a[pivotindex]);
                }
                else
                {

                    //for (int m = i; m < j; m++)
                    //{
                    //    arr.Add(a[m]);
                    //}

                    //for (int m = i; m < j; m++)
                    //{
                    //    arr.Add(a[m]);
                    //}

                    //int index = a.Length - k;
                    ////return ;
                    //arr.Add(a[index]);
                    //k--;
                }
            }
        }

        //private static int QuickSelect(int[] a, int left, int right, int k)
        //{
        //    int i = left;
        //    int j = right;
        //    int pivotIndex = (left + right) / 2;
        //    int pivotValue = a[pivotIndex];

        //    while (a[i] < pivotValue && i < right)
        //    {
        //        i++;
        //    }
        //    while (a[j] > pivotValue && j > left)
        //    {
        //        j--;
        //    }

        //    if (i <= j)
        //    {
        //        Swap(a, i, j);
        //        i++;
        //        j--;
        //    }

        //    int lessSize = i;
        //    int greaterSize = a.Length - 1 - lessSize;

        //    if (k <= greaterSize)
        //    {
        //        return QuickSelect(a, pivotIndex + 1, right, k);
        //    }
        //    else
        //    {
        //        if (k == (greaterSize + 1))
        //        {
        //            return pivotValue;
        //        }
        //        else
        //        {
        //            int index = a.Length - k;
        //            return a[index];
        //        }
        //    }
        //}

        private static void QuickSort(int[] a, int left, int right)
        {
            int i = left;
            int j = right;
            int pivot = a[(left + right) / 2];

            while ((a[i] < pivot) && (i < right))
            {
                i++;
            }

            while ((pivot < a[j]) && (j > left))
            {
                j--;
            }

            if (i <= j)
            {
                Swap(a, i, j);
                i++;
                j--;
            }

            if (left < j)
            {
                QuickSort(a, left, j);
            }

            if (i < right)
            {
                QuickSort(a, i, right);
            }
        }

        private static void Swap(int[] a, int i, int j)
        {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }

        private static int[] MergeSort(int[] a)
        {
            if (a.Length == 1)
            {
                return a;
            }

            int pivot = a.Length / 2;
            var left = new int[pivot];
            var right = new int[a.Length - pivot];

            for (int i = 0; i < pivot; i++)
            {
                left[i] = a[i];
            }

            for (int j = 0, i = pivot; i < a.Length; i++, j++)
            {
                right[j] = a[i];
            }

            left = MergeSort(left);
            right = MergeSort(right);

            return Merge(left, right);
        }

        private static int[] Merge(int[] left, int[] right)
        {
            var result = new int[left.Length + right.Length];

            int i = 0, j = 0;
            int k = 0;

            while (i < left.Length && j < right.Length)
            {
                if (left[i] == right[j])
                {
                    result[k] = left[i];
                    i++;
                    j++;
                }
                else if (left[i] < right[j])
                {
                    result[k] = left[i];
                    i++;
                }
                else
                {
                    result[k] = right[j];
                    j++;
                }

                k++;
            }

            for (; i < left.Length; i++)
            {
                result[k] = left[i];
                k++;
            }
            for (; j < right.Length; j++)
            {
                result[k] = right[j];
                k++;
            }

            return result;
        }

        private static void InsertionSort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                int k = i;
                int j = i - 1;
                var current = arr[k];

                while (current < arr[j])
                {
                    arr[j + 1] = arr[j];
                    j--;
                    k = j + 1;
                }

                arr[k] = current;
            }
        }

        public static IEnumerable<string> subsetPermutations { get; set; }
    }

    class LLNode
    {
        public int value;
        public LLNode next;
        public LLNode previous;

    }

    class LLNodeRandom
    {
        public int Value;
        public LLNodeRandom Next;
        public LLNodeRandom Random;
    }
}